package io.github.consoles.dsa;

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Created by yiihua-013 on 17/4/5.
 */
public class RandomQueue<Item> implements Iterable<Item> {

    private static final int DEFAULT_CAP = 5;

    private Item[] datas;
    private int    size;

    public RandomQueue() {
        this(DEFAULT_CAP);
    }

    private RandomQueue(int cap) {
        datas = (Item[]) new Object[cap];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private void resize(int len) {
        Item[] newData = (Item[]) new Object[len];
        for (int i = 0; i < size; i++) newData[i] = datas[i];
        datas = newData;
    }

    public void enqueue(Item item) {
        if (size == datas.length) resize(2 * size);
        datas[size++] = item;
    }

    /**
     * 随机返回并且删除该元素
     *
     * @return
     */
    public Item dequeue() {

        if (isEmpty()) throw new NoSuchElementException("随机队列为空!");

        int  index = (int) (Math.random() * (size - 1));
        Item tmp   = datas[index];
        datas[index] = datas[size - 1];
        datas[size - 1] = null;

        size--;
        if (size == datas.length / 4) resize(datas.length / 2);

        return tmp;
    }

    /**
     * 随机返回一个元素但是并不删除它
     *
     * @return
     */
    public Item sample() {

        int index = (int) (Math.random() * size);
        return datas[index];
    }

    private class RandomIterator implements Iterator<Item> {

        Item[] dest = Arrays.copyOf(datas, size);

        int index = 0;

        RandomIterator() {
            for (int i = 0; i < dest.length; i++) {
                int  index = (int) (i + Math.floor(Math.random() * (dest.length - i)));
                Item tmp   = dest[i];
                dest[i] = dest[index];
                dest[index] = tmp;
            }
        }

        @Override
        public boolean hasNext() {
            return index != dest.length;
        }

        @Override
        public Item next() {
            return dest[index++];
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new RandomIterator();
    }
}
